#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param s: a string
    @return: return a integer
    """
    def longestValidParentheses(self, s):
        self.stack = []
        self.pos_count = [0] * (len(s) + 1)
        self.max_count = 0
        self.cur_count = 0

        for idx, c in enumerate(s):
            idx += 1        # 下表从1开始

            # print(idx, c)
            if c == '(':
                self.stack.append(idx)
                self.pos_count[idx] = 0
                # self.cur_count = 0
                self.reset_count()

            elif c == ')':
                # 干活的地方到了
                if self.stack and s[self.stack[-1] - 1] == '(':
                    match_idx = self.stack.pop()
                    self.cur_count += 2                              # 层级嵌套
                    self.cur_count += self.pos_count[ match_idx - 1] # 并行等级/相同等级 的括号
                    self.pos_count[idx] = self.cur_count

                    # print("match")
                else:
                    # 崩了, 不匹配
                    self.reset()

            else:
                assert False, "not valid character:" +  idx + c


            print(self.max_count)
            print()

        return max(self.max_count, self.cur_count)

    def reset(self):
        self.reset_count()
        self.stack.clear()

    def reset_count(self):
        self.max_count = max(self.max_count, self.cur_count)
        self.cur_count = 0


def test():
    s = Solution()
    # ret = s.longestValidParentheses('(()')                # 2
    # ret = s.longestValidParentheses(')()())()()()')       # 6
    # pars = ")(()(()(((())(((((()()))((((()()(()()())())())()))()()()())(())()()(((()))))()((()))(((())()((()()())((())))(())))())((()())()()((()((())))))((()(((((()((()))(()()(())))((()))()))())"

    pars = ")(((((()())()()))()(()))("      # 22

    ret = s.longestValidParentheses(pars)
    print(ret)


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
